//package _dp_base;
//
///**
// * 96. 不同的二叉搜索树
// */
//public class No96 {
//    private int[] cache;
//
//    public int numTrees(int n) {
//        cache = new int[20];
//        return dfs(n);
//    }
//
//    private int dfs(int i) {
//        if (cache[i] != 0) return cache[i];
//
//        //如果只有0，或者1个节点，则可能的子树情况为1种
//        if (i == 0 || i == 1) return cache[i] = 1;
//
//        int count = 0;
//        for (int j = 1; j <= i; j++) {
//            //当用i这个节点当做根节点时
//            //左边有多少种子树
//            int leftNum = dfs(j - 1);
//            //右边有多少种子树
//            int rightNum = dfs(i - j);
//            //乘起来就是当前节点的子树个数
//            count += leftNum * rightNum;
//        }
//
//        return cache[i] = count;
//    }
//}
